# -*- coding: utf-8 -*-
# @Time    : 2021/1/2 下午12:17
# @Author  : tgy
# https://leetcode-cn.com/problems/sliding-window-maximum/


class Solution:

    def maxSlidingWindow(self, nums, k):
        ...
        result = []
        if not nums or k < 0:
            return []

        if k == 1:
            return nums

        # 存放索引
        deque = []
        for i in range(len(nums)):

            while deque and nums[deque[-1]] < nums[i]:
                deque.pop()

            deque.append(i)

            if i >= k - 1:
                if deque[0] < i - k + 1:
                    deque.pop(0)
                result.append(nums[deque[0]])

        return result


if __name__ == '__main__':
    ...
    solution = Solution()
    # window = solution.maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)
    window = solution.maxSlidingWindow([1, 3, 1, 2, 0, 5], 3)
    print(window)
